package com.gframework.datastructure.trie;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 这是一个<strong>线程安全的</strong>，支持设置自定义分隔符的trie树，分隔符默认是'.'，既以点进行分割.<br>
 * <p>
 * SeparatorTrieTree树不会以字符作为公共前缀标识，而是以一个长字符串，根据分隔符进行分割。例如：
 * 
 * <pre>
 * 存储：
 * user.id
 * user.name
 * 那么树的结构就是
 * user|
 * {@code ----|----id}
 * {@code ----|----name}
 * </pre>
 * </p>
 * 
 * @since 1.0.0
 * @author Ghwolf
 * @param <T> 存储内容的类型
 * @see WildcardTrieTree
 */
public class SeparatorTrieTree<T> implements StorageTrieTree<T> {
	
	/**
	 * 默认分隔符
	 */
	private static final char DEFAULT_SEPARATOR = '.';
	/**
	 * 根节点
	 */
	private Node root = new Node();
	/**
	 * 单词分隔符
	 */
	private final char separator ;

	/**
	 * 节点类
	 * 
	 * @since 1.0.0
	 * @author Ghwolf
	 */
	class Node {

		/** 子叶子节点对象 */
		private volatile Map<String, Node> leaf;
		/** 当前节点存储的数据 */
		private AtomicReference<T> value = new AtomicReference<>();
		
		/**
		 * 取得当前Node的leaf节点存储map对象
		 */
		public Map<String,Node> getLeaf() {
			if (this.leaf == null) {
				synchronized(this) {
					if (this.leaf == null) {
						this.leaf = new ConcurrentHashMap<>();
					}
				}
			}
			return this.leaf;
		}
		/**
		 * 是否有叶子节点
		 */
		public boolean hasLeaf() {
			return leaf != null && leaf.size() != 0 ;
		}
		/**
		 * 取得当前节点的存储对象
		 * @return 返回存储的对象，没有返回null
		 */
		public T getValue() {
			return this.value.get();
		}
		/**
		 * 设置一个value，并返回旧的value
		 * @param value 要设置的value
		 * @return 返回旧的value，如果没有返回null
		 */
		public T setValue(T value) {
			T t ;
			do {
				t = this.value.get();
			} while(!this.value.compareAndSet(t,value));
			return t ;
		}
		/**
		 * 直接删除一个叶子节点
		 * @param key 要删除的叶子节点
		 */
		public void removeLeaf(String key) {
			this.leaf.remove(key);
		}
		/**
		 * 仅删除当前节点的value值，并返回
		 * @return 返回被删除的数据，没有返回null
		 */
		public T removeValue() {
			return this.setValue(null);
		}
		/**
		 * 删除当前节点的叶子节点下指定key值的Node，如果该Node下的叶子节点为null，则该叶子节点也会被删除。否则只删除数据。
		 * @param key 要删除的叶子节点key
		 */
		@SuppressWarnings("unchecked")
		public T removeLeafNodeIfEmpty(String key) {
			Object[] arr = new Object[1];
			this.leaf.computeIfPresent(key, (k,v) -> {
				arr[0] = v.removeValue();
				return v.hasLeaf() ? v : null;
			});
			return (T) arr[0];
		}
	}
	
	/**
	 * 创建一个以'.'进行分割的trie树.
	 */
	public SeparatorTrieTree(){
		this(DEFAULT_SEPARATOR);
	}
	
	/**
	 * 创建一个具有指定分隔符的trie树
	 * @param separator 分隔符
	 */
	public SeparatorTrieTree(char separator){
		this.separator = separator;
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public T find(String key) {
		this.checkKey(key);
		return find0(key);
	}
	
	/**
	 * 不做参数检查的find操作，主要用于子类灵活扩展
	 */
	protected T find0(String key) {
		String[] params = FastSplitUtil.fastSplit(key,this.separator);
		Node node = this.root;
		for (int x = 0; x < params.length && node != null; x ++) {
			if (node.hasLeaf()) {
				node = node.getLeaf().get(params[x]); 
			} else {
				// 没有此项key的内容
				return null ;
			}
		}
		return node == null ? null : node.getValue();
	}

	/**
	 * 取得根节点对象
	 */
	Node getRoot() {
		return this.root;
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean containsKey(String key) {
		return this.find(key) != null ;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public T removeValue(String key) {
		return this.remove(key,false);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void remove(String key) {
		this.remove(key,true);
	}
	
	private T remove(String key,boolean allLeaf) {
		this.checkKey(key);
		String[] keys = FastSplitUtil.fastSplit(key, this.separator);
		Node node = this.root ;
		for (int x = 0, endSize = keys.length - 1; x < keys.length && node != null; x ++) {
			if (node.hasLeaf()) {
				if (x >= endSize) {
					if (allLeaf) {
						node.removeLeaf(keys[x]);
					} else {
						return node.removeLeafNodeIfEmpty(keys[x]);	
					}
				} else {
					node = node.getLeaf().get(keys[x]);
				}
			} else {
				return null;
			}
		}
		return null ;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public T add(String key, T value) {
		this.checkKey(key);
		if (value == null) {
			return this.removeValue(key);
		}
		String[] keys = FastSplitUtil.fastSplit(key, this.separator);
		Node node = this.root ;
		for (int x = 0 ; x < keys.length ; x ++) {
			Map<String,Node> leaf = node.getLeaf();
			node = leaf.computeIfAbsent(keys[x], k -> new Node());
		}
		return node.setValue(value);
	}

	/**
	 * 取得分隔符
	 * @return 返回分隔符
	 */
	public char getSeparator() {
		return this.separator;
	}
	
	/**
	 * 效验key的合法性
	 * @param key 要判断的key
	 * @throws IllegalArgumentException 参数不合法
	 */
	protected final void checkKey(String key) {
		if (key == null || key.equals("")) 
			throw new IllegalArgumentException("trieTree的节点key不能时null或\"\"。");
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public String getFormatString(String title) {
		StringBuilder value = new StringBuilder(1024);
		value.append("====== " + title + " ======\n");
		final String prefix = "|---";
		
		StringBuilder prefixBuffer = new StringBuilder(prefix);
		Deque<Iterator<Map.Entry<String,Node>>> queue = new ArrayDeque<>();
		queue.add(this.root.getLeaf().entrySet().iterator());
		
		Iterator<Map.Entry<String,Node>> iter;
		
		while( (iter = queue.peek()) != null) {
			boolean pop = true ;
			while(iter.hasNext()) {
				Map.Entry<String,Node> entry = iter.next();
				value.append(prefixBuffer).append(entry.getKey()).append('\n');
				Node n = entry.getValue();
				if (n.hasLeaf()) {
					// 入栈
					prefixBuffer.append(prefix);
					queue.push(n.getLeaf().entrySet().iterator());
					pop = false ;
					break ;
				}
			}
			if (pop) {
				// 出栈
				prefixBuffer.delete(prefixBuffer.length() - prefix.length(), prefixBuffer.length());
				queue.poll();
			}
		}
		
		
		return value.toString();
	}

}
